#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int countPrimes(int n) {
        vector<int> prim;
        vector<bool> st(n + 1, false);
        for (int i = 2; i < n; i++) {
            if (!st[i]) {
                prim.push_back(i);
            }
            for (int j = 0; j < prim.size() && i <= n / prim[j]; j++) {
                // cout<<i*prim[j]<<endl;
                st[i * prim[j]] = true;
                if (i % prim[j] == 0)break;
            }
        }
        return prim.size();
    }
};